섬 연결하기.md

코드

parent=[]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]


def union(a, b):
    a = find(a)
    b = find(b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def solution(n, costs):
    answer = 0
    global parent
    parent=[0]*(n+1)
    for i in range(n+1):
        parent[i]=i

    # 비용을 기준으로 정렬
    costs.sort(key=lambda x:x[2])

    for i in costs:
        a,b,c=i
        # 비용이 낮은거부터 뽑아낸 다음 사이클이 없으면 union
        if find(a)!=find(b):
            union(a,b)
            answer+=c
    return answer